package org.basis.algorithm.promote;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 单调栈练习
 *
 * @author Mr_wenpan@163.com 2022/02/18 11:01
 */
public class MonotonousStack01 {

    public static void main(String[] args) {

    }

    public static int max2(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        int size = arr.length;
        int[] sums = new int[arr.length];
        // 先求每个位置到0位置的和
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = 0; j <= i; j++) {
                sum += arr[j];
            }
            sums[i] = sum;
        }

        int max = Integer.MIN_VALUE;
        // 单调栈（单调递增）
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                Integer popIndex = stack.pop();
                int sum = (stack.isEmpty() ? sums[i - 1] : sums[i - 1] - sums[stack.peek()]) * arr[popIndex];
                max = Math.max(max, sum);
            }
            stack.push(i);
        }

        // 如果栈中还有元素
        while (!stack.isEmpty()) {
            Integer popIndex = stack.pop();
            // 注意：这里是size - 1 因为是最后一个位置上的数来结算的栈中剩余的元素，所以累加和应该求到最后一个位置
            int sum = (stack.isEmpty() ? sums[size - 1] : sums[size - 1] - sums[stack.peek()]) * arr[popIndex];
            max = Math.max(max, sum);
        }

        return max;
    }

    /**
     * 单调栈练习准备(番茄牛腩)
     * 给定一个数x代表在arr中的下标，和一个数组arr，请找到x左右两边比x小的且离x位置最近的数
     */
    public static int[] prepare(int[] arr, int x) {
        int[] res = new int[2];
        int left = x;
        int right = x;
        while (left >= 0) {
            if (arr[left] < x) {
                break;
            }
            left--;
        }
        while (right < arr.length) {
            if (arr[right] < x) {
                break;
            }
            right++;
        }
        if (left < 0) {
            // 表示没有找到
            res[0] = -1;
        } else {
            res[0] = left;
        }
        if (right > arr.length) {
            // 表示没有找到
            res[1] = -1;
        } else {
            res[1] = right;
        }

        return res;
    }

    /**
     * 对数组中的每个位置都找出他左边离他最近且比他小的位置和右边离他最近且比他小的位置的下标
     * 这里arr数组需要满足无重复值，如果是有重复值的话，那么栈里元素面应该用LinkedList类型而不是integer(编码上会复杂一些)
     */
    public static int[][] getNearLessNoRepeat(int[] arr) {

        if (arr == null || arr.length < 1) {
            return null;
        }
        int[][] res = new int[arr.length][2];
        // 单调递增的栈(记录的是下标，这里的递增指的是下标对应的值是递增的)
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            // i位置入栈前先检查栈的单调性
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                // 弹出就记录，记录这个数左右两边比他小的且离他最近的数的下标
                Integer popIndex = stack.pop();
                // 栈为空，则说明左边没有比该位置的数小的数了
                int leftLessThanIndex = stack.isEmpty() ? -1 : stack.peek();
                res[popIndex][0] = leftLessThanIndex;

                // 记录右边，右边离他最近且比他小的数就是让他弹出的那个数，记录他的下标
                res[popIndex][1] = i;
            }
            stack.push(i);
        }

        // 如果栈内还有值，从栈中依次弹出并记录左右两端离他最近且比他小的数的位置（由于是单调递增栈，所以此时栈内右边已经没有比他小的数了，
        // 左边比他小且离他最近的数就是该数压着的那一个）
        while (!stack.isEmpty()) {
            Integer popIndex = stack.pop();
            int leftLessThanIndex = stack.isEmpty() ? -1 : stack.peek();
            res[popIndex][0] = leftLessThanIndex;
            res[popIndex][1] = -1;
        }

        return res;
    }

    /**
     * 获取子数组(暴力法)
     */
    public List<int[]> getSubArray(int[] arr) {

        ArrayList<int[]> result = new ArrayList<>();
        // 每一个位置都求包含他自己的子数组
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int index = 0;
                int[] sub = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    sub[index++] = arr[k];
                }
                result.add(sub);
            }
        }

        return result;
    }

}
